package com.asia.algorithmcode.greedy;

/**
 * 134、加油站
 */
public class CanCompleteCircuit {


    public static void main(String[] args) {
        int[] gas = {1,2,3};
        int[] cost = {3,1,1};
        System.out.println(new CanCompleteCircuit().canCompleteCircuit(gas, cost));
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int cur = 0;
        int start = 0;

        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            cur += diff;
            if (cur < 0) {
                // 说明 start 到 i 都不可能做起点
                start = i + 1;
                cur = 0;
            }
        }

        return total >= 0 ? start : -1;
    }
}
